package com.javabasic.algorithm.cometoj;

import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Scanner;

/*
容易发现满足 f(x) = ⌊x2⌋ 的正整数 x 只有 17, 18，证明如下。
∵ f(x) = ⌊x2⌋
∴ 2f(x) = x or 2f(x) + 1 = x
设 n 为满足上述条件的数
由 n 的位数考虑：
• n 只有一位：设 x = a，则 2a = a or 2a + 1 = a，显然 a 没有 [1, 9] 间
的整数解
• n 有两位：设 x = 10a + b（即 a 是十位， b 是个位），则 2a + 2b =
10a + b or 2a + 2b + 1 = 10a + b
∴ 8a − b = 0 or 8a − b − 1 = 0
∴ a = 1, b = 8 or a = 1, b = 7
∴ n = 18 or n = 17
• n 有三位：设 x = 100a + 10b + c（即 a 是百位， b 是十位， c 是个位），
则 2a + 2b + 2c = 100a + 10b + c or 2a + 2b + 2c + 1 = 100a + 10b + c
∴ 98a + 8b − c = 0 or 98a + 8b − c − 1 = 0
∵ a ≥ 1, b ≥ 1（a 是百位， b 是十位）
∴ c ≥ 108
不满足 c ∈ [1, 9]（c 是个位），故该情况不成立
• 大于三位的，与三位类似，都与个位 ∈ [1, 9] 不符
综上，满足 f(x) = ⌊x2⌋ 的正整数仅有 17, 18。
对于一组询问，判断 17 和 18 是否是 n 的约数即可。
 */
public class 迫真数论 {
    private static Scanner cin = new Scanner(System.in);

    private static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        int t = cin.nextInt();
        int ans = 0;
        while (t-->0) {
            BigInteger num = cin.nextBigInteger();
            ans = 0;
            if (num.mod(BigInteger.valueOf(18)) == BigInteger.ZERO) {
                ans++;
            }
            if (num.mod(BigInteger.valueOf(17)) == BigInteger.ZERO) {
                ans++;
            }
            System.out.println(ans);
        }


    }
}
